In theoretical computer science, a locally testable code is an error correcting code for which membership can be tested by a non-adaptive property testing algorithm. That is, locally testable codes have an efficient probabilistic algorithm that, based on its random bits, non-adaptively looks at few (e.g. a constant number of) positions of the message and can then determine with high probability whether the message is close to a codeword.
Locally testable codes have applications in average-case complexity and the design of probabilistically checkable proofs.
Locally decodable codes are closely related to locally testable codes, in that they make it possible to decode single bits of the message by only looking at few positions of a possibly corrupted codeword.
A family of error-correcting codes Cn ⊆ {0, 1}n is locally testable with soundness s(δ) (where s(δ) < 1 for every δ > 0), and query complexity q(n) if there exists a non-adaptive oracle algorithm T (the tester) that on input 1n and given oracle access to a string y ∈ {0, 1}n satisfies the following:
In theoretical computer science, one is typically interested in locally testable codes whose query complexity is constant or at most logarithmic.
An example of a locally testable code is the Hadamard code. The Hadamard code is testable with 3 queries and soundness 1 - δ.